package com.acyouzi.leetcode.greedy;

/**
 * Created by SUN on 2017/9/6.
 */
public class Candy {
  // https://leetcode.com/problems/candy/description/
  public int candy(int[] ratings) {
    int can[] = new int[ratings.length];
    for (int i = 1 ; i < ratings.length ; i++){
      if (ratings[i-1] < ratings[i]) can[i]=can[i-1]+1;
    }
    for (int i = ratings.length-2; i >=0 ; i--) {
      if (ratings[i+1] < ratings[i]) can[i] = Math.max(can[i],can[i+1]+1);
    }
    int res = 0;
    for (int i = 0; i < ratings.length; i++) {
      res = res + 1 + can[i];
    }
    return res;
  }
}
